package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class MinimumDepthOfBinaryTree {

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    // 我理解 DFS 深度优先遍历 和 BFS 层序遍历
    class Solution {
        public int minDepth(TreeNode root) {
            if(root == null) return 0;
            int minDepth = 1;
            // 层序遍历开始找
            Deque<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            // 入队  offer  出队 pull
            while(!queue.isEmpty()){
                int s = queue.size();
                for(int i =0;i<s;i++){
                    TreeNode node = queue.poll();
                    if(node.left == null && node.right == null){
                        return minDepth;
                    }
                    if(node.left != null){
                        queue.offer(node.left);
                    }
                    if(node.right != null){
                        queue.offer(node.right);
                    }
                }
                minDepth++; // 每多遍历一行 就加1
            }
            return minDepth;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    
    public static void main(String[] args) {
        Solution solution = new MinimumDepthOfBinaryTree().new Solution();
        // put your test code here
        //[3,9,20,null,null,15,7] 帮我生成一下测试用例
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
    }
}